#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
#include "tree.h"

using namespace std;

void flatHelper(Tree *root, Tree *&start, Tree *&end)
{
    if (!root) {
	return;
    }

    if (root->data == 1) 
	int test = 0;

    if (!root->left && !root->right) {start = root; end = root; return;}
    Tree *leftStart = NULL, *leftEnd = NULL, *rightStart = NULL, *rightEnd = NULL;
    flatHelper(root->left, leftStart, leftEnd);    
    flatHelper(root->right, rightStart, rightEnd);    
    root->left = NULL;
    if (leftStart) root->right = leftStart;
    else root->right = rightStart;
    if (leftEnd) leftEnd->right = rightStart;
    if (rightStart) rightStart->left = leftEnd;
    start = root;
    if (rightStart) end = rightEnd;
    else end = leftEnd;
    Tree *cur = start;
    while (cur) {
	cout << cur->data << " ";
	cur = cur->right;
    }
    cout << endl;
}

void flat(Tree *root)
{
    Tree *start = NULL, *end = NULL;
    flatHelper(root, start, end);
    Tree *cur = start;
    while (cur) {
	cout << cur->data << " ";
	cur = cur->right;
    }
}

//add much better code 
void flatterHelper(TreeNode *root, TreeNode *&pre)
{
    if (!root) return;
    pre->right = root;
    pre = pre->right;
    TreeNode *right = pre->right;
    TreeNode *left = pre->left;
   // pre->right = NULL;
   pre->left = NULL;
    flatterHelper(left, pre);
    flatterHelper(right, pre);
}
    
        void flatten(TreeNode *root) {
            TreeNode *head= new TreeNode(0);
            TreeNode *pre = head;
            flatterHelper(root, pre);
            root = head->right;
        }  

int main(int argc, char **argv)
{
  //  int input[] = {21,7,5,6,3,2,1,4,6,11,35,56};
    int input[] = {1, 2};
    int input2[] = {6,23,43,54,12,54,8,10,11,35,56};
    //int input[] = {7};
    Tree *root = NULL, *root2 = NULL;
    int result;

    for (int i = 0; i < sizeof(input)/sizeof(int); i++) {
        TreeInsert(root, input[i]);
    }

    print_ascii_tree(root);
    flat(root);
}
